Bäume (Trees) & Traversierung

IN-SA TB #033+

---

Nicht-lineare Datenstrukturen

Neben linearen Strukturen (Liste, Queue, Stack) gibt es auch nicht-lineare Datenstrukturen:

• Bäume (Trees)
• Graphen

---

① Baum (Tree)

Rekursive Definition

Ein Baum ist entweder:

• ein einzelner Knoten, oder
• ein als Wurzel dienender Knoten, der mit einer Menge von Bäumen (Teilbäumen) verbunden ist

Alternative Definition

Eine Baumstruktur ist eine hierarchische Struktur, die aus Knoten und Kanten (Verbindungen) besteht.

          Wurzel
         /  |  \
       [B1][B2][B3]
       / \      |
     [B4][B5]  [B6]
               / \
             [B7][B8]   ← Blätter (Grad 0)

Begriffe

Begriff	Definition
Wurzel	Der einzige Knoten im Baum, der keinen Vorgänger hat
Blatt	Knoten ohne Nachfolger (Grad 0)
Teilbaum	Jeder zusammenhängende Teil eines Baumes ist wieder ein Baum
Grad eines Knotens	Anzahl der Nachfolger eines Knotens
Pfad	Weg über die Kanten des Baumes von einem Knoten zu einem anderen (Richtung: Wurzel → Blatt)
Tiefe / Höhe	Anzahl der Kanten (oder Knoten) im längsten Pfad des Baumes

Tiefe – Beispiele

Zählen der Kanten:              Zählen der Knoten:

nichts   → Tiefe -1             nichts   → Tiefe 0
  O      → Tiefe  0               O      → Tiefe 1
 / \     → Tiefe  1              / \     → Tiefe 2
O   O                           O   O

Wichtige Anmerkungen

• Ein Baum enthält NIE einen zyklischen Pfad
• Strukturen mit zyklischen Pfaden nennt man Graphen
• Eine lineare (verkettete) Liste ist ein Baum vom Grad 1

Klassendiagramm (UML)

┌──────────────────────────────┐
│            Tree              │
├──────────────────────────────┤
│ - head : Datentyp            │
│ - tree1 : Tree               │
│ - tree2 : Tree               │
│ - tree3 : Tree               │
│   ...                        │
│ - treeN : Tree               │
└──────────────────────────────┘

---

② Binärbaum (BinTree)

Definition

Ein Binärbaum ist ein Baum, bei dem jeder Knoten höchstens 2 Kinder (Nachfolger) hat – also Grad 0, 1 oder 2.

Varianten

Variante	Beschreibung
Voller Binärbaum	Jeder Knoten hat genau 0 oder 2 Kinder
Vollständiger Binärbaum	Alle Ebenen sind vollständig gefüllt, Blätter auf gleicher Höhe

Klassendiagramm (UML)

┌──────────────────────────────┐
│           BinTree            │
├──────────────────────────────┤
│ - head : Datentyp            │
│ - leftTree : BinTree         │
│ - rightTree : BinTree        │
├──────────────────────────────┤
│ + Operationen...             │
└──────────────────────────────┘

Beispiel-Binärbaum

              8
            /   \
           4    12
          / \   / \
         2   6 10  14
        /\  /\  \   \
       1  3 5  7 11  13

---

Traversierung von Bäumen

Unter Traversierung versteht man das systematische Besuchen jedes Knotens in einem Baum.

Es gibt drei klassische Traversierungsarten:

---

Inorder (LWR – Links, Wurzel, Rechts)

Rekursive Regel:

1. Gehe in den linken Teilbaum (und wende dort Inorder an)
2. Besuche die Wurzel – gib sie aus
3. Gehe in den rechten Teilbaum (und wende dort Inorder an)

Ergebnis beim Beispielbaum:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14

Inorder bei einem Suchbaum liefert die Elemente in sortierter Reihenfolge!

---

Preorder (WLR – Wurzel, Links, Rechts)

Rekursive Regel:

1. Besuche die Wurzel – gib sie aus
2. Gehe in den linken Teilbaum
3. Gehe in den rechten Teilbaum

---

Postorder (LRW – Links, Rechts, Wurzel)

Rekursive Regel:

1. Gehe in den linken Teilbaum
2. Gehe in den rechten Teilbaum
3. Besuche die Wurzel – gib sie aus

Beispiel-Ausgabe Postorder:

1, 3, 2, 5, 7, 6, 4, 9, 11, 10, 13, 15, 14, 12, 8

---

Vergleich der Traversierungen

Traversierung	Reihenfolge	Merkformel
Inorder	Links → Wurzel → Rechts	LWR
Preorder	Wurzel → Links → Rechts	WLR
Postorder	Links → Rechts → Wurzel	LRW

Implementierung in Python

class BinTree:
    def __init__(self, head=None, left=None, right=None):
        self.__head = head
        self.__left = left
        self.__right = right

    def inorder(self):
        if self.__left is not None:
            self.__left.inorder()       # 1. Linker Teilbaum
        print(self.__head)              # 2. Wurzel ausgeben
        if self.__right is not None:
            self.__right.inorder()      # 3. Rechter Teilbaum

    def preorder(self):
        print(self.__head)              # 1. Wurzel ausgeben
        if self.__left is not None:
            self.__left.preorder()      # 2. Linker Teilbaum
        if self.__right is not None:
            self.__right.preorder()     # 3. Rechter Teilbaum

    def postorder(self):
        if self.__left is not None:
            self.__left.postorder()     # 1. Linker Teilbaum
        if self.__right is not None:
            self.__right.postorder()    # 2. Rechter Teilbaum
        print(self.__head)              # 3. Wurzel ausgeben

---

Graphen

Ein Graph ist eine Verallgemeinerung des Baumes:

• Besteht aus Knoten und Kanten
• Darf zyklische Pfade enthalten (im Gegensatz zum Baum)
• Ein Baum ist also ein Graph ohne zyklischen Pfad

    A ── B
    |  × |
    C ── D

Strukturen mit zyklischen Pfaden nennt man Graphen.

---

Zusammenfassung: Dynamische Datenstrukturen

Dynamische Datenstrukturen
        │
        ├── Lineare Strukturen
        │        ├── Verkettete Liste
        │        ├── Queue (FIFO)
        │        └── Stack (LIFO / FILO)
        │
        └── Nicht-lineare Strukturen
                 ├── Bäume
                 │    ├── Allgemeiner Baum
                 │    └── Binärbaum
                 └── Graphen